package demo1;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    public String reverseStr(String s, int k) {
        char[] array = s.toCharArray();
        for (int i = 0; i < array.length; i += 2 * k) {
            reverse(array, i, i + k);
        }
        return new String(array);
    }

    /**
     * [start,end)
     *
     * @since 2025/1/31 9:17
     */
    private void reverse(char[] array, int start, int end) {
        if (end > array.length) {
            end = array.length;
        }
        end--;

        char tmp;
        while (start < end) {
            // swap
            tmp = array[start];
            array[start] = array[end];
            array[end] = tmp;
            // move index
            start++;
            end--;
        }
    }

    public List<String> validStrings(int n) {
        List<String> list = new ArrayList<>();
        dfs(1 << n, n-1, list);
        return list;
    }
    private void dfs(int p, int bit, List<String> list) {
        if (bit < 0) {
            String s = Integer.toBinaryString(p);
            list.add(s.substring(1));
            return;
        }
        dfs(p|(1 << bit), bit-1, list);
        if ((p & (1 << (bit+1))) != 0) {
            dfs(p, bit-1, list);
        }
    }
}
